package offer_test_40;

import struct.LinkedNode;
import struct.MyStack;

//输入两个链表，找出它们的第一个公共结点。
public class seventeen_FirstCommonNodesInLists {
	public static void main(String[] args) {
		LinkedNode head1 = new LinkedNode();
		LinkedNode second1 = new LinkedNode();
		LinkedNode third1 = new LinkedNode();
		LinkedNode forth1 = new LinkedNode();
		LinkedNode fifth1 = new LinkedNode();
		LinkedNode head2 = new LinkedNode();
		LinkedNode second2 = new LinkedNode();
		LinkedNode third2 = new LinkedNode();
		LinkedNode forth2 = new LinkedNode();
		head1.next = second1;
		second1.next = third1;
		third1.next = forth1;
		forth1.next = fifth1;
		head2.next = second2;
		second2.next = forth1;
		third2.next = fifth1;
		head1.data = 1;
		second1.data = 2;
		third1.data = 3;
		forth1.data = 6;
		fifth1.data = 7;
		head2.data = 4;
		second2.data = 5;
		third2.data = 6;
		forth2.data = 7;
		System.out.println(getFristCommonNode(head1, head2).data);
	}

	public static LinkedNode getFristCommonNode(LinkedNode one, LinkedNode two) {
		MyStack onestrack = new MyStack(100);
		MyStack twostrack = new MyStack(100);
		putInStack(onestrack, one);
		putInStack(twostrack, two);
		LinkedNode commonnde=new LinkedNode();
		while (!onestrack.isEmpty() && !twostrack.isEmpty()) {
			LinkedNode tempone = (LinkedNode) onestrack.pop();
			LinkedNode temptwo = (LinkedNode) twostrack.pop();
			if (!tempone.equals(temptwo)) {
				return commonnde;
			}
			commonnde=tempone;
		}
		return commonnde;
	}

	public static void putInStack(MyStack s, LinkedNode node) {
		while (node != null) {
			s.push(node);
			node = node.next;
		}
	}
}
